The invention provides a solution for the following general problem. At first blush, this problem may appear purely hypothetical, however, such a problem does exist in the real world, and the invention provides a solution to the problem.
A "writer" stores logical zeroes and ones in locations of a table stored in a memory. During the writing, some arbitrary procedure, chosen by the writer, selects the addresses and values to be stored in the memory locations. After the memory locations have been written, the writer is denied write access to the memory.
Subsequently, an "adversary" permutes (scrambles) the address lines to the memory in some unknown manner, that is, the adversary secretly switches the address lines around.
A "reader" who knows the procedure used by the writer, but not the permutation applied by the adversary, must use the permuted address lines to correctly read the values stored in the memory by the writer. The goal is to discover how the address lines were permuted by the adversary, of course, without the adversary's cooperation, and, in addition, to have the writer communicate a message to the reader that is as large as possible using the memory as the communication channel.
In the real world, one type of circuit component that is sometimes used by system designers is a Field-Programmable Gate Array (FPGA). FPGAs combine the flexibility of software, and the speed of hardware. FPGAs are frequently used in applications where specialized high-speed processing of digital signals (data) is required: processing that would be unsuitable for general purpose processors executing conventional software. Typical applications where FPGAs can be found include: real-time video signal processing, data reformatting, pattern recognition, and data encryption. FPGAs are especially attractive to a one-of-a-kind or low volume designs where the development of traditional hardware solutions would be too costly and time-consuming.
Generally, FPGAs comprise the following basic components: input and output pins connected to internal pads, logic resources, flip-flops, and routing resources. The logic resources often are multiple replications of the same logic building blocks. For example, an elementary block of logic can be a look-up table (LUT) with two, three, four, or five inputs (address) lines. The LUTs are like ROMs or some other interconnected arrangement of gates that provide an equivalent functionality. For some LUTs, it is possible to actually write the "truth table" of the LUT and thus use the LUT as a RAM.
For all the FPGAs, the programmable gates are configured by a configuration bitstream produced by an FPGA software tool from a "design" corresponding to the application to be implemented in the FPGA. For example, the logic elements of a "design" can be implemented using the equivalent of Read-only Memory (ROM) elements configured as a look-up table (LUT). In essence, the LUT operates as a logical function, input value on "address" lines are used to "index" the LUT and corresponding logical values (zeroes and ones) stored in the LUT at the indexed address are returned as output values, hence a transformation.
To set initial logical values in an FPGA LUT, for example, initializing a truth table when part of the FPGA is used as logic function, the input is specified as part of the FPGA "circuit" in source design form. The source design is processed by the FPGA design tools to obtain a new configuration for the FPGA. The FPGA tools perform operations such as mapping the logic parts of the design to the elementary logic elements of the FPGA, placing those mapped elements, and routing the wiring between the elements. After the mapping, placement and routing phases, the tools have the complete map of all the configuration that the FPGA needs to perform according to the original design. From this map, the tools generate a configuration bitstream ready to be downloaded to the FPGA. Once configured, the FPGA can be used according to the design.
These FPGA design tools, depending on the complexity of the source design, take anywhere from minutes to hours to complete their processing of the source design definitions. After the FPGA has been configured, data can be processed.
For some application, such as pattern matching and encryption, it is beneficial, in terms of silicon space and speed, to produce slightly different instances of the "design" for each different pattern or key processed, rather than using a single "design" accepting different patterns or keys, with all the machinery to load and store new patterns or keys. For example, if a user key is used to encrypt user data, then the key needs to be changed for every different user. In such applications, circuits used to load different keys would take extra space. For these applications, it would be useful to be able to change directly the small part of the "design" that is specific to a key or pattern directly in the configuration bitstream, rather than to do a full FPGA tool cycle each time. Also, if the changes have to be made outside of a development environment, for example, in an FPGA embedded in an end-user machine, then the FPGA design tools may not be readily available to change the run time values.
FIG. 1 shows the phases and general data flow of a traditional FPGA design cycle. The input to the flow is some source design 110 that includes logic elements 111 and 112, where 112 is a particular element that fits into one of the elementary LUTs of the FPGA, a four-input LUT in FIG. 1. The source design 110 transforms some input data to output data 114. The source design 110 includes, for example, logical elements S.sub.0, S.sub.1, S.sub.2, and S.sub.3 that are to process input data connected to inputs x.sub.0, x.sub.1, x.sub.2, x.sub.3 of a LUT 112 of the FPGA by lines 115. The elements 111 are arbitrary, what is of interest here is the input data on lines 115. Most of the FPGAs are based on either 3 or 4 or 5 input table LUTs as elementary logic blocks.
In this case, the LUT 112 is "indexed" according to the data on the four inputs x.sub.0, x.sub.1, x.sub.2, x.sub.3 115. For each input value in the range of 0 to 15, the LUT 112 provides either a zero or a one as output on line 114. In other words, the LUT 112 stores sixteen zero or one bits in a vector that form the truth table for the possible input data values, and the logic elements are to be combined to perform some function f(x.sub.0, x.sub.1, x.sub.2, x.sub.3) on the input data to produce output bits on line 114. Note that logical element S.sub.0 is connected to input x.sub.0, and so forth.
In phase 10, the design tools take the source design 110 to generate a "mapped" design 120 for the actual target FPGA. Note, the mapped design 120 does not directly correspond to the original source design 110. After the source design 110 has been mapped by the tools, a configuration bitstream 131 is produced.
A shaded portion 132 of the configuration bitstream 131 corresponds to the initial sixteen values (x . . . x) of the LUT 112. Tables 133 and 134 respectively show a mapping of a function as determined in the source, and comparable function g as determined by the tools. The positions of the bits are shown as in hexadecimal (bold) and binary form. At this point, note that these are different, in other words, function g is a permutation of functions f. The values (x, . . . , x) 132 in the bitstream 131 contain no indication how they are ordered.
For applications like the ones presented above, where the "design" has to be slightly changed, usually values of LUTs, FIG. 2 shows the major steps of the prior art design process 200. A source design 210 and initial values 220 are presented to FPGA design tools 230, as in phase 10 of FIG. 1. The tools 230 produce a configuration bitstream 240. In step 250, the configuration bitstream is loaded into the FPGA, and the mapped design is used during a "run." In step 260, a decision is made to process data with different initial values, and steps 230 and 240 are repeated. For a complex design, each cycle may take hours with static assignment of new initial values at the start of each cycle.
During the mapping phase 10 of FIG. 1 or step 230 of FIG. 2, some tools allow the designer to explicitly specify the correspondence between the logical source address lines and the physical placement of the lines to an FPGA internal structure. In this case, there is less difficulty. However, many tools do not provide for this correspondence, and may scramble the input lines to the LUT in some unknown permuted manner. Therein lies the problem. Going back to FIG. 1, the relationship between the functions f and g with respect to like bits in part 132 are completely unknown.
For a conventional application, where the initial values are statically determined and do not need to change for each run, the unknown permutation on internal inputs is not a problem. This is true because the tools make sure that the overall outcome is logically correct with respect to the source design, no matter what the implementation of the mapped design. In addition, the time required to map the source to the physical wiring of the FPGA is not a concern. However, explicit input placement may limit the ability of the tools to optimally place and route the circuits, and in some cases, explicit placement makes it impossible for the tools to map the source to a working arrangement.
For some applications, it may be desired to allow the initial values to be modified dynamically during the operation of the FPGA without having to resort to a lengthy run of the FPGA tools. For example, periodically, new initial values would be patched directly into the configuration bitstream, and the FPGA is "reconfigured" on-the-fly. This could only be done if the ordering of the input on the LUT, and other like FPGA structures is known. If the ordering is known, then truth table bits can be put in the configuration bitstream in the correct order without having to suffer a full design cycle.
The purpose of the invention is to discover the permutation that FPGA design tools introduce between the order of inputs of internal components, such as LUTs, as specified in a source design and the order in an actual physical mapping of the design. If the ordering can be determined, then dynamic modification of LUT values becomes possible.